package com.cat.dynamicPlanning;


/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/ugly-number-ii/
 * @create 2025/8/26 17:24
 * @since JDK17
 */

public class Solution05 {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2, i2 = 1, i3 = 1, i5 = 1, cur = 1; i <= n; i++) {
            int a = dp[i2] * 2;
            int b = dp[i3] * 3;
            int c = dp[i5] * 5;
            cur = Math.min(a, Math.min(b, c));
            if (cur == a) {
                i2++;
            }
            if (cur == b) {
                i3++;
            }
            if (cur == c) {
                i5++;
            }
            dp[i] = cur;
        }
        return dp[n];
    }
}
